#include <iostream>
#include <vector>
#include <map>
#include <ctime>
#include <cassert>
#include <Windows.h>
using namespace std;

template <typename T, typename U>
class AvlMap
{
	struct TNode
	{
		TNode(const T &k): key(k), bf(0), lchild(0), rchild(0) {}
		TNode(const T &k, const U &v): key(k), val(v), bf(0), lchild(0), rchild(0) {}
		TNode *lchild;
		TNode *rchild;
		T key;
		U value;

		// balance factor: the height of left subtree minus the height of right subtree. -1 ,0 or 1
		//
		int bf;		
	};

public:	AvlMap()
		{
			root = NULL;
		}

		~AvlMap()
		{
			clear();
		}

		void insert(const T &key, const U &val)
		{
			bool taller;
			TNode *nd = insertAndAdjust(root, key, taller);
			nd->value = val;
		}

		U& operator[](const T &key)
		{
			bool taller;
			TNode *nd = insertAndAdjust(root, key, taller);
			return nd->value;
		}

		bool contain(const T &key)
		{
			return getNode(root, key) != NULL;
		}

		// if key exists then return true and the val will be assigned, otherwise return false
		bool tryGet(const T &key, U &val)
		{
			TNode *nd = getNode(root, key);
			if (nd)
			{
				val = nd->value;
				return true;
			}
			return false;
		}

		// if key exists then return true and the val will be modified, otherwise return false
		bool tryUpdate(const T &key, const U &val)
		{
			TNode *nd = getNode(root, key);
			if (nd)
			{
				nd->value = val;
				return true;
			}
			return false;
		}

		// if key doesn't exist return false
		bool remove(const T &key)
		{
			bool shorter;
			return removeAndAdjust(root, key, shorter);
		}

		bool empty()
		{
			return root == NULL;
		}

		void clear()
		{
			destroyTree(root);
			root = NULL;
		}

		//unsigned int size() const
		//{
		//}

private:
	TNode *getNode(TNode *nd, const T &key) 
	{
		if (nd == NULL)
			return NULL;

		if (key < nd->key)
			return getNode(nd->lchild, key);
		else if (key == nd->key)
			return nd;
		else
			return getNode(nd->rchild, key);
	}

	// if the key has already existed, then return that the pointer to that pointer
	TNode *insertAndAdjust(TNode *&nd, const T &key, bool &taller)
	{
		if (nd == NULL)
		{
			nd = new TNode(key);
			taller = true;
			return nd;
		}

		if (key < nd->key)
		{
			TNode *res = insertAndAdjust(nd->lchild, key, taller);
			if (taller)
			{
				switch (nd->bf)
				{
				case -1: nd->bf = 0; taller = false; break;
				case 0: nd->bf = 1; taller = true; break;
				case 1:
					{
						if (key < nd->lchild->key)
						{
							// left subtree of the node nd->lchild
							// case left left, right rotation
							//
							nd->bf = 0;
							nd->lchild->bf = 0;
							taller = false;
							right_rotation(nd);
						}
						else
						{
							// right subtree of the node nd->lchild
							// case left right, first left rotation then right rotation
							// 
							TNode *lc = nd->lchild;
							TNode *lrc = lc->rchild;
							switch (lrc->bf)
							{
							case -1: lc->bf = 1; nd->bf = 0; break;
							case 0: lc->bf = 0; nd->bf = 0; break;
							case 1: lc->bf = 0; nd->bf = -1; break;
							}
							lrc->bf = 0;
							taller = false;
							left_rotation(nd->lchild);
							right_rotation(nd);
						}
						break;
					}
				}
			}
			return res;
		}
		else if (key > nd->key)
		{
			TNode *res = insertAndAdjust(nd->rchild, key, taller);
			if (taller)
			{
				switch (nd->bf)
				{
				case -1:
					{
						if (key < nd->rchild->key)
						{
							// right subtree of the node nd->lchild
							// case right left, first right rotation then left rotation
							// 
							TNode *rc = nd->rchild;
							TNode *rlc = rc->lchild;
							switch (rlc->bf)
							{
							case -1: nd->bf = 1; rc->bf = 0; break;
							case 0: nd->bf = 0; rc->bf = 0; break;
							case 1: nd->bf = 0; rc->bf = -1; break;
							}
							rlc->bf = 0;
							taller = false;
							right_rotation(nd->rchild);
							left_rotation(nd);
						}
						else
						{
							// right subtree of the node nd->lchild
							// case right right
							// 
							nd->bf = 0;
							nd->rchild->bf = 0;
							taller = false;
							left_rotation(nd);
						}
						break;
					}
				case 0: nd->bf = -1; taller = true; break;
				case 1: nd->bf = 0; taller = false; break;
				}
			}
			return res;
		}
		else
		{
			taller = false;
			return nd;
		}
	}

	bool removeAndAdjust(TNode *&nd, const T &key, bool &shorter)
	{
		if (nd == NULL)
		{
			shorter = false;		
			return false;
		}

		if (key < nd->key)
		{
			bool res = removeAndAdjust(nd->lchild, key, shorter);
			if (shorter)
			{
				// left subtree
				//				
				switch (nd->bf)
				{
				case -1:
					{
						switch (nd->rchild->bf)
						{
						case 1:
							{
								int tmp = nd->rchild->lchild->bf;
								right_rotation(nd->rchild);
								left_rotation(nd);
								nd->bf = 0;
								shorter = false;
								switch (tmp)
								{
								case - 1: nd->lchild->bf = 1; nd->rchild->bf = 0; break;
								case 0: nd->lchild->bf = nd->rchild->bf = 0; break;
								case 1: nd->lchild->bf = 0; nd->rchild->bf = -1; break;
								}
								break;
							}
						case 0: left_rotation(nd); nd->bf = 1; nd->lchild->bf = -1; shorter = false; break;
						case -1: left_rotation(nd); nd->bf = 0; nd->lchild->bf = 0; shorter = true; break;
						}
						break;
					}
				case 0: nd->bf = -1; shorter = false; break;
				case 1: nd->bf = 0; shorter = true; break;
				}
			}
			return res;
		}
		else if (key > nd->key)
		{
			bool res = removeAndAdjust(nd->rchild, key, shorter);
			// right subtree
			// 
			if (shorter)
			{
				switch (nd->bf)
				{
				case -1: nd->bf = 0; shorter = true; break;
				case 0: nd->bf = 1; shorter = false; break;
				case 1: 
					{
						switch (nd->lchild->bf)
						{
						case -1:
							{
								int tmp = nd->lchild->rchild->bf;
								left_rotation(nd->lchild);
								right_rotation(nd);
								nd->bf = 0;
								shorter = false;
								switch (tmp)
								{
								case -1: nd->lchild->bf = 1; nd->rchild->bf = 0; break;
								case 0: nd->lchild->bf = 0; nd->rchild->bf = 0; break;
								case 1: nd->lchild->bf = 0; nd->rchild->bf = -1; break;
								}
								break;
							}
						case 0: nd->bf = -1; nd->rchild->bf = 1; shorter = false; break;
						case 1: nd->bf = 0; nd->rchild->bf = 0; shorter = true; break;
						}
						break;
					}
				}
			}
			return res;
		}
		else
		{
			if (nd->lchild && nd->rchild)
			{
				swapWithSuccessor(nd, nd->rchild, shorter);
				// right subtree
				//
				if (shorter)
				{
					switch (nd->bf)
					{
					case -1: nd->bf = 0; shorter = true; break;
					case 0: nd->bf = 1; shorter = false; break;
					case 1: 
						{
							switch (nd->lchild->bf)
							{
							case -1:
								{
									int tmp = nd->lchild->rchild->bf;
									left_rotation(nd->lchild);
									right_rotation(nd);
									nd->bf = 0;
									shorter = false;
									switch (tmp)
									{
									case -1: nd->lchild->bf = 1; nd->rchild->bf = 0; break;
									case 0: nd->lchild->bf = 0; nd->rchild->bf = 0; break;
									case 1: nd->lchild->bf = 0; nd->rchild->bf = -1; break;
									}
									break;
								}
							case 0: nd->bf = -1; nd->rchild->bf = 1; shorter = false; break;
							case 1: nd->bf = 0; nd->rchild->bf = 0; shorter = true; break;
							}
							break;
						}
					}
				}
			}
			else if (nd->lchild)
			{
				TNode *tmp = nd->lchild;
				delete nd;
				nd = tmp;
				shorter = true;
			}
			else
			{
				TNode *tmp = nd->rchild;
				delete nd;
				nd = tmp;
				shorter = true;
			}
			return true;
		}
	}

	void swapWithSuccessor(TNode *a, TNode *&nd, bool &shorter)
	{
		if (nd->lchild != NULL)
		{
			swapWithSuccessor(a, nd->lchild, shorter);
			if (shorter)
			{
				// always in the left subtree
				// 
				switch (nd->bf)
				{
				case -1:
					{
						switch (nd->rchild->bf)
						{
						case 1:
							{
								int tmp = nd->rchild->lchild->bf;
								right_rotation(nd->rchild);
								left_rotation(nd);
								nd->bf = 0;
								shorter = false;
								switch (tmp)
								{
								case - 1: nd->lchild->bf = 1; nd->rchild->bf = 0; break;
								case 0: nd->lchild->bf = nd->rchild->bf = 0; break;
								case 1: nd->lchild->bf = 0; nd->rchild->bf = -1; break;
								}
								break;
							}
						case 0: left_rotation(nd); nd->bf = 1; nd->lchild->bf = -1; shorter = false; break;
						case -1: left_rotation(nd); nd->bf = 0; nd->lchild->bf = 0; shorter = true; break;
						}
						break;
					}
				case 0: nd->bf = -1; shorter = false; break;
				case 1: nd->bf = 0; shorter = true; break;
				}
			}
		}
		else
		{
			a->key = nd->key;
			a->value = nd->value;
			TNode *tmp = nd->rchild;
			delete nd;
			nd = tmp;
			shorter = true;
		}
	}

	void right_rotation(TNode *&nd)
	{
		TNode *lc = nd->lchild;
		nd->lchild = lc->rchild;
		lc->rchild = nd;
		nd = lc;
	}

	void left_rotation(TNode *&nd)
	{
		TNode *rc = nd->rchild;
		nd->rchild = rc->lchild;
		rc->lchild = nd;
		nd = rc;
	}

	void destroyTree(TNode *tree)
	{
		if (tree)
		{
			destroyTree(tree->lchild);
			destroyTree(tree->rchild);
			delete tree;
		}
	}

private:
	TNode *root;
};


void test_insertion()
{
	srand(time(0));
	map<int, int> mp;
	AvlMap<int, int> am;

	const int len = 10000;
	for (int i = 0; i < len; i++)
	{
		int key = rand() * rand();
		int value = rand();
		mp[key] = value;
		am[key] = value;
	}
	for (map<int, int>::iterator i = mp.begin(); i != mp.end(); i++)
	{
		assert(i->second == am[i->first]);
	}
}

void test_remove()
{
	srand(time(0));
	map<int, int> mp;
	AvlMap<int, int> am;
	//TreapMap<int, int> tm;
	map<int, int> src;

	const int len = 1000000;
	for (int i = 0; i < len; i++)
	{
		//int key = rand() * rand();
		int key = i;
		int value = rand();
		src[key] = value;
	}
	
	DWORD ta = GetTickCount();
	for (map<int, int>::iterator i = src.begin(); i != src.end(); i++)
	{
		mp[i->first] = i->second;
	}
	DWORD tb = GetTickCount();
	for (map<int, int>::iterator i = src.begin(); i != src.end(); i++)
	{
		am[i->first] = i->second;
	}
	DWORD tc = GetTickCount();
	//for (map<int, int>::iterator i = src.begin(); i != src.end(); i++)
	//{
	//	tm[i->first] = i->second;
	//}
	DWORD td = GetTickCount();
	cout << tb - ta << endl << tc - tb << endl << td - tc << endl;

	DWORD t1 = GetTickCount();
	int cnt = 0;
	map<int, int>::iterator i = src.begin();
	for (; cnt < len / 2; i++, cnt++)
	{
		mp.erase(i->first);
	}
	DWORD t2 = GetTickCount();
	cnt = 0;
	i = src.begin();
	for (; cnt < len / 2; i++, cnt++)
	{
		am.remove(i->first);
	}
	DWORD t3 = GetTickCount();
	cnt = 0;
	i = src.begin();
	//for (; cnt < len / 2; i++, cnt++)
	//{
	//	tm.remove(i->first);
	//}
	DWORD t33 = GetTickCount();
	cout << t2 - t1 << endl << t3 - t2 << endl << t33 - t3 << endl;;

	map<int, int>::iterator mid = i;
	DWORD t4 = GetTickCount();
	map<int, int>::iterator iend;
	for (map<int, int>::iterator j = mid; j != src.end(); j++)
	{
		mp.find(j->first);
	}
	DWORD t5 = GetTickCount();
	for (map<int, int>::iterator j = mid; j != src.end(); j++)
	{
		am.contain(j->first);
	}
	DWORD t6 = GetTickCount();
	//for (map<int, int>::iterator j = mid; j != src.end(); j++)
	//{
	//	tm.contain(j->first);
	//}
	DWORD t7 = GetTickCount();

	cout << t5 - t4 << endl << t6 - t5 << endl << t7 - t6 << endl;
	for (map<int, int>::iterator i = src.begin(); i != mid; i++)
		if (am.contain(i->first))
			cout << "error";
}



void performance_test()
{
	srand(time(0));

	// sorted and random data
	const int len2 = 200000;
	vector<pair<int, int> > data2;
	map<int, int> mp2;
	AvlMap<int, int> am2;

	for (int i = 0; i < len2; i++)
	{
		//data2.push_back(make_pair(rand() * rand(), rand()));
		data2.push_back(make_pair(i, rand() * rand()));
	}

	DWORD t4 = GetTickCount();
	for (int i = 0; i < len2; i++)
		mp2[data2[i].first] = data2[i].second;

	DWORD t5 = GetTickCount();
	for (int i = 0; i < len2; i++)
		am2[data2[i].first] = data2[i].second;

	DWORD t6 = GetTickCount();
	for (int i = 0; i < len2; i++)
		mp2[data2[i].first] = 1;

	DWORD t7 = GetTickCount();
	for (int i = 0; i < len2; i++)
		am2.tryUpdate(data2[i].first, 1);

	DWORD t8 = GetTickCount();


	cout << "Sorted data:\n";
	cout << "Insertion: "<< t5 - t4 << '\t' << t6 - t5 << endl;
	cout << "Query: "<< t7 - t6 << '\t' << t8 - t7 << endl;
}

int main()
{
	test_remove();
	system("pause");
	return 0;
}